#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    vector<vector<string>> res;
    bool check(const string& str)
    {
        int left = 0, right = str.size() - 1;
        while (left < right)
        {
            if (str[left++] != str[right--])
                return false;
        }
        return true;
    }
    void dfs(const string& str, int start, vector<string>& cut)
    {
        if (start == str.size())
        {
            res.push_back(cut);
            return;
        }
        for (int end = start; end < str.size(); ++end)
        {
            if (check(str.substr(start, end - start + 1)))
            {
                cut.push_back(str.substr(start, end - start + 1));
                dfs(str, end + 1, cut);
                cut.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string& s) {
        int n = s.size();
        vector<string> tmp;
        dfs(s, 0, tmp);
        return res;
    }
};